#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef map<ll, ll> mll;
ll n, k;
int P;
int A[100];
ll d[20][65537+10];
int pw[100];
//mll d[20];

//void  add(mll& a, const mll& b, int mod){
//    for(const auto &it:b){
//        a[(mod+it.second)%P]++;
//        a[it.first] += it.second;
//    }
//}
//
//void operator +=(mll& a, const mll& b){
//    for(auto it:b){
//        a[it.first] += it.second;
//    }
//}

//mll dp(int p, int mod, bool flg){
//    if(!p) {
//        mll m;
//        m[mod] = 1;
//        return m;
//    }
////    if(flg && !d[p].empty())
////        return d[p];
//    int x = flg?1:A[p];
//    mll ans;
//    for (int i = 0; i <= x; ++i) {
//        if(!d[p-1].empty())
//            add(ans, d[p-1], mod);
//        else{
//            mll t = dp(p-1, (mod*3+i)%P, flg||i<x);
//            ans += t;
//        }
//    }
//    if(flg)
//        d[p] = ans;
//    return ans;
//}

ll dp(int p, int mod, int flg){
    if(!p) return mod==k;
    if(flg && d[p][mod]) return d[p][mod];
    int x = flg?1:A[p];
    ll ans = 0;
    for (int i = 0; i <= x; ++i) {
        ans += dp(p-1, (mod+i*pw[p])%P, flg||i<x);
    }
    if(flg) d[p][mod] = ans;
    return ans;
}

int cal(int x){
    int p = 0;
    while (x){
       A[++p] = x%2;
       x/=2;
    }
    return p;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin >> n >> P;
    pw[0] = 1;
    for (int i = 1; i < 100; ++i) {
        pw[i] = pw[i-1]*3%P;
    }
    int p = cal(n);
    ll ans = 0;
    for(k=0; k<P; ++k){
        memset(d, 0, sizeof d);
        ll t = dp(p, 0, false);
        if(!k) --t;
        ans ^= t;
    }
//    mll m = cal(n);
//    m[0]--;
//    for(auto it:m) ans ^= it.second;
    cout << ans;
    return 0;
}